package com.leet.competition;

import java.util.Arrays;

public class NumOfString {
    //输入：nums = [1,2,3,4,5]
    //输出：[1,2,4,5,3]
    //解释：
    //i=1, nums[i] = 2, 两相邻元素平均值为 (1+4) / 2 = 2.5
    //i=2, nums[i] = 4, 两相邻元素平均值为 (2+5) / 2 = 3.5
    //i=3, nums[i] = 5, 两相邻元素平均值为 (4+3) / 2 = 3.5

    //输入：nums = [6,2,0,9,7]
    //输出：[9,7,6,2,0]
    //解释：
    //i=1, nums[i] = 7, 两相邻元素平均值为 (9+6) / 2 = 7.5
    //i=2, nums[i] = 6, 两相邻元素平均值为 (7+2) / 2 = 4.5
    //i=3, nums[i] = 2, 两相邻元素平均值为 (6+0) / 2 = 3
        int flag = 0;
        public int latestDayToCross(int row, int col, int[][] cells) {
            int day = cells.length;
            int[][] visited = new int[row][col];
            int[][] m = new int[row][col];
            for(int[] cell:cells){
                m[cell[0]-1][cell[1]-1] = 1;
            }
            for(int i = cells.length; i >= 0; i--){
                for(int j = 0; j < col; j++){
                    if(cells[0][j]!=1){
                        dfs(0,i,cells,visited,m);
                        if(flag == 1) return i;
                    }
                }
                int[] cell = cells[i-1];
                m[cell[0]-1][cell[1]-1] = 0;
            }
            return 0;
        }
        void dfs(int row, int col, int[][] cells,int[][] visited,int[][] m){
            if(row < 0 || row > m.length-1 || col < 0 || col > m[0].length-1
                    || visited[row][col] == 1 || m[row][col] == 1){
                return;
            }
            visited[row][col] = 1;
            if(row == m.length-1){
                flag = 1;
                return;
            }
            dfs(row+1,col,cells,visited,m);
            dfs(row-1,col,cells,visited,m);
            dfs(row,col+1,cells,visited,m);
            dfs(row,col+1,cells,visited,m);
            visited[row][col] = 0;
            return;
        }
}
